package algorithm.slidingWindow;

import java.util.LinkedList;

public class GasStation {
    public static int canCompleteCircuit(int[] cost, int[] gas){
        int[] arr = new int[cost.length * 2];
        for (int i = 0; i < arr.length; i++) {
            if(i < cost.length){
                arr[i] = gas[i] - cost[i];
            }else {
                arr[i] = gas[i - cost.length] - cost[i - cost.length];
            }
        }
        boolean[] booleans = goodArray(arr);
        for (int i = 0; i < booleans.length; i++) {
            if(booleans[i])
                return i;
        }
        return -1;
    }

    public static boolean[] goodArray(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i];
        }
        int w = arr.length / 2;
        boolean[] result = new boolean[w];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int R = 0; R < arr.length - 1; R++) {
            while(!queue.isEmpty() && arr[queue.peekLast()] >= arr[R])
                queue.pollLast();
            queue.addLast(R);
            int pre = R <= w - 1? 0 : arr[R - w];
            if(R >= w - 1){
                if(arr[queue.peekFirst()] - pre >= 0)
                    result[R - w + 1] = true;
                else
                    result[R - w + 1] = false;
            }
            if(queue.peekFirst() == R - w + 1)
                queue.pollFirst();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        int i = canCompleteCircuit(cost, gas);
        System.out.println(i);
    }


}
